﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PexExamplesPermutations
{
    public class Anagrams
    {

        static bool Anagram(string word1, string word2)
        {
            Contract.Requires(word1 != null);
            Contract.Requires(word2 != null);
	    List<string> permutations = GetAllPermutations(word1);
            return permutations.Contains(word2);
        }

        public static List<string> GetAllPermutations(string input)
        {
            List<string> permutations = new List<string>();
            if (input.Length == 0) { 
                permutations.Add(""); 
            }
            else
            {
                permutations = GetAllPermutations(input.Substring(1,input.Length-1));
                permutations = interleave(input[0], permutations);
            }

            return permutations;
        }

        public static List<string> interleave(char elem, List<string> list)
        {
            List<string> res = new List<string>();
            foreach (string l in list) 
            {
                if (l.Length == 0)
                {
                    res.Add(elem.ToString());
                }
                else
                {
                    for (int i = 0; i <= l.Length; i++)
                    {
                        string nl = l.Substring(0, i) + elem.ToString() + l.Substring(i, l.Length - i);
                        res.Add(nl);
                    }
                }
            }
            return res;
        }

        public static void Main()
        {
            string word1 = "cat";
            string word2 = "tac";

            Console.WriteLine(Anagram(word1, word2));

            string word3 = "cat";
            string word4 = "dog";

            Console.WriteLine(IsAnagram(word3, word4));
            Console.ReadKey();
        }

    }
}
